// @algorithm @lc id=207 lang=cpp 
// @title course-schedule


// @test(2,[[1,0]])=true
// @test(2,[[1,0],[0,1]])=false
enum State {
    TO_LEARN = 0,
    LEARNING,
    FINISHED,
};
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> dG(numCourses); // [course] --> [ next courses ... ]
        for(auto & req : prerequisites)
            dG[ req[1] ].push_back( req[0] );

        vector<int> cs(numCourses, TO_LEARN);
        function<bool(int)> CanLearn = [&](int i){
            if(cs[i] == FINISHED)
                return true;

            cs[i] = LEARNING;
            for(auto next : dG[i])
                if(cs[next] == LEARNING || !CanLearn(next))
                    return false;

            cs[i] = FINISHED;
            return true;
        };

        for(int i=0; i<numCourses; i++)
            if(!CanLearn(i)) return false;
        return true;
    }
};